//
// Created by yanhai on 2021/1/10.
//

/**
 * 查找链表倒数第N个节点
 */

#include <stdio.h>
#include "link_common.h"

/**
 * 查找倒数第N个节点
 * 原理：让第1个指针先走n步，第2个指针再和第1个指针一起后移，
 *      当第1个指针到最后时，第2个指针指向的就是倒数第N个节点
 * 注意：链表长度是否大于等于N
 * @param T
 * @param n 无符号整形
 * @return
 */
link_node *find_nth_to_tail(link *T, unsigned int n)
{
    if (n == 0) return NULL;

    int distance = 0;
    link_node *p1, *p2;

    p1 = p2 = T->root;

    while (p2 != NULL) {
        p2 = p2->next;

        if (distance == n) {
            p1 = p1->next;
        } else {
            distance++;
        }
    }

    // distance < n 表示链表长度小于n
    return distance == n ? p1 : NULL;
}

/**
 * 测试
 * @param T
 * @param n
 */
void find_nth_to_tail_test(link *T, unsigned int n)
{
    link_node *node = find_nth_to_tail(T, n);
    if (node != NULL) {
        printf("倒数第%u个元素的值为: %d\n", n, node->key);
    } else {
        printf("倒数第%u个元素不存在\n", n);
    }
}

int main()
{
    link T = link_create_from_index(20, false);
    link_print(&T);

    // 正常情况与异常情况
    find_nth_to_tail_test(&T, 14);  // 正常情况
    find_nth_to_tail_test(&T, 1);   // 临界值
    find_nth_to_tail_test(&T, 20);  // 临界值
    find_nth_to_tail_test(&T, 22);  // 超出链表长度
    find_nth_to_tail_test(&T, 0);   // n值非法
    find_nth_to_tail_test(&T, -4);  // n值非法

    link_destroy(&T);
    return 0;
}
